import collections


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = 0

class Encrypter(object):

    def __init__(self, keys, values, dictionary):
        """
        :type keys: List[str]
        :type values: List[str]
        :type dictionary: List[str]
        """
        n = len(keys)
        self.kv = {keys[i]: values[i] for i in range(n)}
        self.vk = collections.defaultdict(set)
        for i in range(n):
            self.vk[values[i]].add(keys[i])
        self.root = TreeNode('#')
        for index, word in enumerate(dictionary):
            node = self.root
            for w in word:
                if w in node.neighbors:
                    node = node.neighbors[w]
                else:
                    new_node = TreeNode(w)
                    node.neighbors[w] = new_node
                    node = new_node
            node.flag = 1

    def encrypt(self, word1):
        """
        :type word1: str
        :rtype: str
        """
        ans = [self.kv[w] for w in word1]
        return ''.join(ans)

    def decrypt(self, word2):
        """
        :type word2: str
        :rtype: int
        """
        m = len(word2)
        ans = []
        self.count = 0

        def dfs(node, i):
            if i == m:
                if node.flag:
                    self.count += 1
            else:
                w = word2[i: i + 2]
                for v in self.vk[w]:
                    if v in node.neighbors:
                        ans.append(v)
                        dfs(node.neighbors[v], i + 2)
                        ans.pop()

        dfs(self.root, 0)
        return self.count


data = Encrypter(["a", "b", "c", "z"], ["aa", "bb", "cc", "zz"],
                 ["aa", "aaa", "aaaa", "aaaaa", "aaaaaaa"])
print(data.decrypt("aa"))
